package offer.day28;

public class No46GetTranslationCount {
    /*
     * 面试题46：把数字翻译成字符串
     * 题目：给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成a，1翻译成b，。。。，25翻译成z
     * 一个数字可能有多种翻译。
     * 例如，12258有5种翻译，分别是bccfi,bwfi,bczi,mcfi,mzi
     * 请编程实现一个函数，用力啊计算一个数字有多少种不同的编译方法
     *
     *
     * 思路：动态规划的思路进行解题，自下而上解决子问题
     * 从数字的末尾开始，然后从右到左翻译并计算不同翻译的数目
     * f(r-2) = f(r-1) + g(r-2,r-1)*f(r)
     *
     *
     * */
    public static void main(String[] args) {
        System.out.println("-10翻译为字符串的数目为："+getTranslationCount(-10));

        System.out.println("1234翻译为字符串的数目为："+getTranslationCount(1234));

        System.out.println("12258翻译为字符串的数目为："+getTranslationCount(12258));
    }

    private static int getTranslationCount(int num) {
        if(num<0){
            return 0;
        }
        return getTranslationCount(Integer.toString(num));
    }

    private static int getTranslationCount(String num){
        int[] dp=new int[num.length()+1];
        int len=dp.length;
        dp[len-1]=0;
        dp[len-2]=1;
        for(int i=len-3;i>=0;i--){
            if(Integer.parseInt(num.charAt(i)+""+num.charAt(i+1))<26){
                dp[i]=dp[i+1]+dp[i+2];
            }else{
                dp[i]=dp[i+1];
            }
        }
        return dp[0];
    }
}
